package tianhao.luo.algorithm;

import java.util.Arrays;

/**
 * 迪杰斯特拉算法
 *
 * @author: tianhao.luo@hand-china.com 2021/7/3  下午3:10
 */
public class DijkstraAlgorithm {


    static class Graph {
        /**
         * 顶点数组
         */
        private char[] vertx;
        /**
         * 邻接矩阵
         */
        private int[][] matrix;

        /**
         * 已经访问的顶点的集合
         */
        private VisitedVertx visitedVertx;


        public Graph(char[] vertx, int[][] matrix) {
            this.vertx = vertx;
            this.matrix = matrix;
        }

        public void show() {
            for (int i = 0; i < matrix.length; i++) {
                System.out.println(Arrays.toString(matrix[i]));
            }
        }

        public void showDijkstra(){
            visitedVertx.show();
        }

        /**
         * @param index 出发顶点对应的下标
         */
        public void dsj(int index) {
            visitedVertx = new VisitedVertx(vertx.length, index);

            // 更新index顶点到周围顶点的距离和前驱顶点
            update(index);

            // 从下一个点开始向后访问
            for (int i = 1; i < vertx.length; i++) {
                // 选择并返回新的访问结点
                index = visitedVertx.updateArr();
                update(index);
            }

        }

        /**
         * 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点.
         *
         * @param index 顶点索引
         */
        private void update(int index) {

            int len = 0;
            // 根据遍历我们的邻接矩阵的matrix[index]行
            for (int i = 0; i < matrix[index].length; i++) {
                // len含义是:出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和
                len = visitedVertx.getDis(index) + matrix[index][i];
                // 如果i顶点没有被访问过,并且len小于出发顶点到j顶点的距离,就需要分析
                if (!visitedVertx.in(i) && len < visitedVertx.getDis(i)) {
                    // 更新i顶点的前驱为index
                    visitedVertx.updatePre(i, index);
                    // 更新出发顶点到i顶点的距离
                    visitedVertx.updateDis(i, len);
                }
            }
        }
    }

    /**
     * 已访问集合
     */
    static class VisitedVertx {
        // 记录各个顶点是否被访问过,1表示访问过,0表示未访问过
        public int[] alreadyArr;
        // 每个下标对应的值为前一个顶点下标,会动态更新
        public int[] preVisited;
        // 记录出发顶点到其他所有顶点的距离,比如G为出发点,就会记录G到其他顶点的距离,会动态更新,求的最短路径距离就会放入dis中
        public int[] dis;

        /**
         * @param length 表示顶点的个数
         * @param index  出发顶点对应的下标,比如G顶点,下标就是6
         */
        public VisitedVertx(int length, int index) {
            this.alreadyArr = new int[length];
            this.preVisited = new int[length];
            this.dis = new int[length];
            // 初始化dis数组
            Arrays.fill(dis, 65535);
            // 设置出发顶点被访问过
            alreadyArr[index] = 1;
            // 设置出发顶点的访问距离为0
            this.dis[index] = 0;
        }

        /**
         * 判断index下标对应的顶点是否被访问过;
         *
         * @param index 索引
         * @return 如果访问过, 就返回true, 否则返回false
         */
        public boolean in(int index) {
            return alreadyArr[index] == 1;
        }

        /**
         * 更新出发顶点到index顶点的距离
         *
         * @param index 索引
         * @param len   权值
         */
        public void updateDis(int index, int len) {
            dis[index] = len;
        }

        /**
         * 更新pre这个顶点的前驱结点为index这个结点
         *
         * @param pre
         * @param index
         */
        public void updatePre(int pre, int index) {
            preVisited[pre] = index;
        }

        /**
         * 返回出发顶点到index这个顶点的距离
         *
         * @param index
         */
        public int getDis(int index) {
            return dis[index];
        }


        /**
         * 继续选择并返回新的访问顶点,比如这里的G,完成后,就是A点作为新的访问顶点(注意不是出发顶点)
         *
         * @return 新的访问结点
         */
        public int updateArr() {
            int min = 65535, index = 0;
            for (int i = 0; i < alreadyArr.length; i++) {
                if (alreadyArr[i] == 0 && dis[i] < min) {
                    min = dis[i];
                    index = i;
                }
            }
            // 更新index顶点被访问过
            alreadyArr[index] = 1;
            return index;
        }

        /**
         * 显示最后的结果
         * 将三个数组展示出来
         */
        public void show() {
            System.out.println("已经访问的结点");
            System.out.println(Arrays.toString(alreadyArr));
            System.out.println("前驱结点");
            System.out.println(Arrays.toString(preVisited));
            System.out.println("dis");
            System.out.println(Arrays.toString(dis));

        }
    }


}
